/******************************************
Cola_implementacion_heap.java
Universidad del Valle de Guatemala
Algoritmos y Estructura de Datos
Autor:
    Martín Guzmán
Fecha: 01 de septiembre de 2009
Descripción: 
*******************************************/
import java.util.ArrayList;
import java.lang.reflect.Array;
import java.lang.AssertionError;
import java.util.Comparator;
import java.util.Vector;

public class Cola_implementacion_heap<G> implements Interfaz_cola<G>, Comparator<Nodo> {
    private Vector<Nodo<G>> heap;
    private int cant;
    private int max;
    private boolean se_pudo;


    //método constructor
    public Cola_implementacion_heap(int max){
        this.max=max;
        cant=0;
        heap = new Vector(max);//para hacer un vector de la cantidad de elementos
    }


    //método para ver si la pila está vacía
    public boolean empty() {
        boolean temporal=true;
        if(this.cant>0){
            temporal=false;
        }
        return temporal;
    }

    //método para sacar el último elemento de la pila
    public G pop() {
        Nodo raiz = heap.firstElement();
        cant--;
        heap.set(0,heap.get(cant));
        mover_abajo(0);
        return (G)raiz.getValor();
    }
    

    //método para que ingrese un nuevo elemento a la pila
    public void push(int val, G Elemento_G) {
        //System.out.println(val);//TODO quitar esto
        if(cant>=max)
            se_pudo=false;
        else{
            se_pudo=true;
            heap.add(cant,new Nodo(val,Elemento_G));
            mover_arriba(cant);
            cant++;
        }

    }

    //método para bajar un nodo de posición
    //Sirve para ajustar el nodo en la posición correcta
    public void mover_abajo(int val) {
        int index_Mayor;
        Nodo hasta_arriba = heap.get(val);
        while (val<cant/2){
            int hijoIzq = 2*val+1;
            int hijoDer = hijoIzq+1;
            if(hijoDer<cant && compare(heap.get(hijoIzq), heap.get(hijoDer))==-1)
                index_Mayor=hijoDer;
            else
                index_Mayor=hijoIzq;

            if(compare(hasta_arriba,heap.get(index_Mayor))>=0)
                break;
            heap.set(val,heap.get(index_Mayor));
            val=index_Mayor;

        }
        heap.set(val, hasta_arriba);
    }

    //método para subir un nodo de posición
    //sirve cuando se inserta un nuevo nodo, para
    //colocarlo en su lugar correcto
    public void mover_arriba(int val) {
        int padre= (val-1)/2;
        Nodo ultimo = heap.get(val);

        while(val>0 && compare(heap.get(padre),ultimo)==-1){
            heap.set(val,heap.get(padre));
            val=padre;
            padre=(padre-1)/2;
        }
        heap.set(val,ultimo);
    }

    //método para comparar los valores de los nodos
    public int compare(Nodo arg0, Nodo arg1) {

        int val1=arg0.getNumero();
        int val2=arg1.getNumero();

        if(val1<val2)//si el primero es más grande
            return 1;
        else if(val2<val1)//si el 2 es más grande
            return -1;
        return 0; //si son iguales
    }

}